package leet63uniquepath63

// https://leetcode.cn/problems/unique-paths-ii/
// 63. Unique Paths II
// 思路：
//  1. dp[i][j]表示到达(i,j)的路径数
//  2. 状态转移方程：
//     dp[i][j] = dp[i-1][j] + dp[i][j-1]
//     dp[i][j] = 0 if grid[i][j] == 1
//  3. 临界值:
//     dp[0][0] = 1
//     dp[0][j] = dp[0][j-1] if grid[0][j] == 0
//     dp[i][0] = dp[i-1][0] if grid[i][0] == 0
//  4. 返回值: dp[m-1][n-1]
//  5. 时间复杂度: O(m*n)
//  6. 空间复杂度: O(m*n)
func UniquePathsWithObstacles(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	// 临界值
	// 如果起点或终点是障碍物，返回0
	if grid[0][0] == 1 || grid[m-1][n-1] == 1 {
		return 0
	}
	// dp[i][j]表示到达(i,j)的路径数
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	// 初始化
	dp[0][0] = 1 // 起点
	// 第一列
	for i := 1; i < m; i++ {
		// 这个判断还是挺巧妙的，如果当前不是障碍物，才可以用上一个的值。当然上一个有可能就是障碍物，但是不重要，因为他是0。
		// 如果是障碍物，dp[i][0] 必然是 0，也就是直接使用默认值0，所以这个else分支可以省略。
		// 其实也可以换一个思路，把这个判断放到for循环的判断里，这样就直接break掉了，可以省掉一些不必要的循环。
		if grid[i][0] == 0 {
			dp[i][0] = dp[i-1][0]
		}
	}
	// 第一行
	for j := 1; j < n; j++ {
		if grid[0][j] == 0 {
			dp[0][j] = dp[0][j-1]
		}
	}
	// 其余的格子就是正常的状态转移了，不过当前的格子是障碍物的时候，dp[i][j] = 0
	// 也就是不需要赋值了，默认值就是0
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if grid[i][j] == 0 {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[m-1][n-1]
}
